package com.leetcode.search.bfs;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/7/25 16:50
 */
public class NumSquares_279 {

    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }

    public int numSquares2(int n) {
        // 生成平方数序列
        List<Integer> squares = generateSquares(n);
        Queue<Integer> queue = new LinkedList<>();
        // 记录该值是否已经出现
        boolean[] marked = new boolean[n + 1];
        queue.offer(n);
        marked[n] = true;
        int level = 0;
        while (!queue.isEmpty()) {
            // 需要以这个点开始延伸一圈
            int size = queue.size();
            level++;
            while (size-- > 0) {
                int cur = queue.poll();
                // 遍历所有平方数
                for (int s : squares) {
                    int next = cur - s;
                    // 如果小于0，说明此时无法由平方和组成
                    if (next < 0) break;
                    // 等于0，说明找到了最小的平方和数，返回level
                    if (next == 0) return level;
                    // 如果已经出现过了，那么跳过
                    if (marked[next]) continue;
                    marked[next] = true;
                    // 把所有平方和加入
                    queue.offer(next);
                }
            }
        }
        return n;
    }

    private List<Integer> generateSquares(int n) {
        List<Integer> squares = new ArrayList<>();
        int index = 1, square = 1;
        while (square <= n) {
            squares.add(square);
            index++;
            square = index * index;
        }
        return squares;
    }

    static class Solution2 {
        Set<Integer> squares = new HashSet<>();

        public int numSquares(int n) {
            for (int i = 0; i * i <= n; i++) {
                squares.add(i * i);
            }

            int count = 1;
            for (; count <= n; count++) {
                if (isDividedBy(n, count)) {
                    return count;
                }
            }
            return count;
        }

        private boolean isDividedBy(int num, int count) {
            if (count == 1) {
                return squares.contains(num);
            }

            for (Integer square : squares) {
                if (isDividedBy(num - square, count - 1))
                    return true;
            }

            return false;
        }

    }

    static class Solution3 {

        public int numSquares(int n) {
            List<Integer> squares = generateSquares(n);
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(n);
            boolean[] marked = new boolean[n + 1];
            int level = 0;
            // BFS -- 通过搜索周边延伸的枝叶 -- 贪心法的迭代模式
            while (!queue.isEmpty()) {
                int size = queue.size();
                level++;
                while (size-- > 0) {
                    int now = queue.poll();
                    // 有可能出现1 4 9 然后 再 9 4 1这种情况，为了避免，添加一个marked数组，防止重复寻找，实现剪枝
                    if (marked[now]) continue;
                    marked[now] = true;
                    // 计算所有减去平方数的节点
                    for (int square : squares) {
                        // 由于迭代具有顺序性，当出现小于情况时，后续的一定都小于，可以直接break
                        if (now < square) {
                            break;
                        } else if (now > square) {
                            queue.offer(now - square);
                        } else if (now == square) {
                            return level;
                        }
                    }
                }
            }
            return level;
        }

        private List<Integer> generateSquares(int n) {
            List<Integer> squares = new ArrayList<>();
            int index = 1, square = 1;
            while (square <= n) {
                squares.add(square);
                index++;
                square = index * index;
            }
            return squares;
        }

    }

}

